package leetCode;

public class t69 {
    public static void main(String[] args) {

        System.out.println(Solution.mySqrt(2147483647));
    }
    static class Solution {
        public static int mySqrt(int x) {

            int leftIndex=0;
            int rightIndex=x;
            long mid=x;
            while (leftIndex<=rightIndex){
                mid=(leftIndex+rightIndex)/2;
                if (mid*mid==x){
                    return (int)mid;
                }else if(mid*mid>x){
                    rightIndex=(int)mid-1;
                }else {
                    leftIndex=(int)mid+1;
                }
            }
            if (mid*mid>x){
                return (int)mid-1;
            }else {
                return (int)mid;
            }
        }
    }
}
